<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT">










<meta name="description" content="传统深度学习模型 RNN和CNN 在欧几里得空间数据(语言，图像，视频等)上取得了不错的成绩，但是在对非欧几里得空间数据(eg：社交网络、蛋白质间的相互作用等)进行处理上却存在一定的局限性，例如：CNN的卷积核在非欧几里得结构化数据上无法保持平移不变性，通俗理解就是在拓扑图中每个结点的相邻结点都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算。">
<meta property="og:type" content="article">
<meta property="og:title" content="GNN系列一：GNN基础知识介绍">
<meta property="og:url" content="http://yoursite.com/2019/08/14/GNN系列一：GNN基础知识介绍/index.html">
<meta property="og:site_name" content="MARS">
<meta property="og:description" content="传统深度学习模型 RNN和CNN 在欧几里得空间数据(语言，图像，视频等)上取得了不错的成绩，但是在对非欧几里得空间数据(eg：社交网络、蛋白质间的相互作用等)进行处理上却存在一定的局限性，例如：CNN的卷积核在非欧几里得结构化数据上无法保持平移不变性，通俗理解就是在拓扑图中每个结点的相邻结点都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算。">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565747219/samples/mars/euclidean_space_xi63na.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565748047/samples/mars/euclidean_data_npttpw.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565748392/samples/mars/non-euclidean_data_wodvez.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565748926/samples/mars/graph_hlft2r.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565750678/samples/mars/adjacency_matrix_jz1gxw.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565750678/samples/mars/degree_matrix_iydlv3.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565750678/samples/mars/example_flm8nd.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565769030/samples/mars/different_variants_of_graph_neural_networks_fqrwma.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565769529/samples/mars/propagation_steps_fmlvgw.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565769528/samples/mars/applications_of_graph_neural_networks_zielmf.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1565751960/samples/mars/gnn_fqjxaf.jpg">
<meta property="og:updated_time" content="2019-09-02T11:05:34.652Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="GNN系列一：GNN基础知识介绍">
<meta name="twitter:description" content="传统深度学习模型 RNN和CNN 在欧几里得空间数据(语言，图像，视频等)上取得了不错的成绩，但是在对非欧几里得空间数据(eg：社交网络、蛋白质间的相互作用等)进行处理上却存在一定的局限性，例如：CNN的卷积核在非欧几里得结构化数据上无法保持平移不变性，通俗理解就是在拓扑图中每个结点的相邻结点都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算。">
<meta name="twitter:image" content="https://res.cloudinary.com/leomars/image/upload/v1565747219/samples/mars/euclidean_space_xi63na.jpg">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2019/08/14/GNN系列一：GNN基础知识介绍/">





  <title>GNN系列一：GNN基础知识介绍 | MARS</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">MARS</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-schedule">
          <a href="/schedule/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-calendar"></i> <br>
            
            日程表
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/08/14/GNN系列一：GNN基础知识介绍/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="MARS">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/messi.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="MARS">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">GNN系列一：GNN基础知识介绍</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-08-14T09:14:43+08:00">
                2019-08-14
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/GNN/" itemprop="url" rel="index">
                    <span itemprop="name">GNN</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2019/08/14/GNN系列一：GNN基础知识介绍/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count gitment-comments-count" data-xid="/2019/08/14/GNN系列一：GNN基础知识介绍/" itemprop="commentsCount"></span>
                </a>
              </span>
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>传统深度学习模型 RNN和CNN 在欧几里得空间数据(语言，图像，视频等)上取得了不错的成绩，但是在对非欧几里得空间数据(eg：社交网络、蛋白质间的相互作用等)进行处理上却存在一定的局限性，例如：CNN的卷积核在非欧几里得结构化数据上无法保持<font color="red"><strong>平移不变性</strong></font>，通俗理解就是在拓扑图中每个结点的相邻结点都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算。</p>
<a id="more"></a>
<p>针对该问题，研究者们引入了图论中抽象意义上的图(Graph)来表示非欧几里得结构化数据，并利用图卷积网络对来图(Graph)数据进行处理，以深入发掘其特征和规律。1、本文首先分别介绍了欧几里得结构化数据和非欧几里得结构化数据特点；2、然后针对非欧几里得结构化数据的表示问题，引入了图论中抽象意义上的图(Graph)概念，并对图(Graph)中一些表示形式进行介绍；3、最后，通过一个简单的例子，对图数据的应用进行介绍，以帮助读者加深对图(Graph)的理解。4、介绍了GNNs原始模型、它的变体和应用场景。</p>
<p>Written By Mars at 2019/08/14 9:30     </p>
<p>Reference：<a href="https://mp.weixin.qq.com/s/sJB4N_ObUqKM8H65yU_1sg" target="_blank" rel="noopener">Datawhale</a> and <a href="https://arxiv.org/pdf/1812.08434" target="_blank" rel="noopener">Review of Graph Neural Networks</a></p>
<h1 id="欧几里得结构化数据"><a href="#欧几里得结构化数据" class="headerlink" title="欧几里得结构化数据"></a>欧几里得结构化数据</h1><h2 id="欧几里得空间"><a href="#欧几里得空间" class="headerlink" title="欧几里得空间"></a>欧几里得空间</h2><p>欧几里德空间(Euclidean Space)，简称为欧氏空间(也可以称为平直空间)，在数学中是对欧几里德所研究的2维和3维空间的一般化。这个一般化把欧几里德对于距离、以及相关的概念长度和角度，转换成任意数维的坐标系。如下图所示。</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565747219/samples/mars/euclidean_space_xi63na.jpg" alt></p>
<p><center>图 a 表示二维欧几里得空间  图 b 表示三维欧几里得空间</center></p>
<h2 id="常见的欧几里得结构化数据"><a href="#常见的欧几里得结构化数据" class="headerlink" title="常见的欧几里得结构化数据"></a>常见的欧几里得结构化数据</h2><p>将数据转换到欧几里得空间中，所得到的数据称为欧几里得结构化数据。常见的欧几里得结构化数据主要包含：</p>
<ul>
<li><p>1D：声音，时间序列等；</p>
</li>
<li><p>2D：图像等；</p>
</li>
<li><p>3D：视频，高光谱图像等。</p>
</li>
</ul>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565748047/samples/mars/euclidean_data_npttpw.jpg" alt></p>
<h1 id="非欧几里得结构化数据"><a href="#非欧几里得结构化数据" class="headerlink" title="非欧几里得结构化数据"></a>非欧几里得结构化数据</h1><h2 id="非欧几里得空间"><a href="#非欧几里得空间" class="headerlink" title="非欧几里得空间"></a>非欧几里得空间</h2><p>科学研究中并不是所有的数据都能够被转换到欧几里得空间中(eg：社交网络、蛋白质间的相互作用等)，对于不能进行欧几里得结构化的数据，我们将其称为非欧几里得结构化数据。</p>
<h2 id="常见的非欧几里得结构化数据"><a href="#常见的非欧几里得结构化数据" class="headerlink" title="常见的非欧几里得结构化数据"></a>常见的非欧几里得结构化数据</h2><ul>
<li><p>1D：社交网络(eg：Facebook，Twitter等)等；</p>
</li>
<li><p>2D：生物网络(基因，分子，大脑连接)等；</p>
</li>
<li><p>3D：基础设施网络(eg：能源，交通，互联网，通信等)等。</p>
</li>
</ul>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565748392/samples/mars/non-euclidean_data_wodvez.jpg" alt></p>
<h1 id="图-Graph"><a href="#图-Graph" class="headerlink" title="图(Graph)"></a>图(Graph)</h1><h2 id="图-Graph-的引入"><a href="#图-Graph-的引入" class="headerlink" title="图(Graph)的引入"></a>图(Graph)的引入</h2><p>针对非欧几里得机构化数据表示问题，研究者引入了图论中抽象意义上的图(Graph)来表示非欧几里得结构化数据。注：这里的Graph是指数学（图论）中的用结点和边建立相对应关系的拓扑图。</p>
<h2 id="图-Graph-的定义"><a href="#图-Graph-的定义" class="headerlink" title="图(Graph)的定义"></a>图(Graph)的定义</h2><p>图(Graph)的定义为$G=(V,E)$，其结构如下图所示：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565748926/samples/mars/graph_hlft2r.jpg" alt><br>上图是一个有标号的简单图，点集和边集分别是：</p>
<p>点集$V=\left\{1,2,3,4,5,6\right\}$；</p>
<p>边集$E=\left\{\left\{1,2\right\}, \left\{1,5\right\},\left\{2,3\right\},\left\{2,5\right\},\left\{3,4\right\},\left\{4,5\right\},\left\{4,6\right\}\right\}$；</p>
<p>其中$V=\left\{ v_i|i=1,\dots,N\right\}$表示节点，$N$表示节点的个数。$E=\left\{e_{ij}|v_i,v_j\in V \right\},|E|\le N^2$表示节点与节点之间所连接的边。</p>
<h2 id="图-Graph-的表示形式"><a href="#图-Graph-的表示形式" class="headerlink" title="图(Graph)的表示形式"></a>图(Graph)的表示形式</h2><h3 id="邻接矩阵-Adjacency-matrix"><a href="#邻接矩阵-Adjacency-matrix" class="headerlink" title="邻接矩阵(Adjacency matrix)"></a>邻接矩阵(Adjacency matrix)</h3><p>邻接矩阵是一个元素为bool值或权值的$N×N$矩阵，该矩阵的定义如下：</p>
<script type="math/tex; mode=display">
A\in \mathbb{R}^{N \times N}, A_{ij}=
\left\{
    \begin{array}{lr}
        a_{ij}\neq 0 & e_{ij}\in \mathcal{E} \\ 
        0 & otherwisw
    \end{array}
\right.</script><p>若图中存在一条连接顶点$v_i$和$v_j$的边$e_{ij}$，则$a_{ij} \neq 0$，否则为0。<strong>当图是稠密时，邻接矩阵是比较合适的表达方法。</strong>如下图所示：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565750678/samples/mars/adjacency_matrix_jz1gxw.jpg" alt></p>
<h3 id="度矩阵-Degree-matrix"><a href="#度矩阵-Degree-matrix" class="headerlink" title="度矩阵( Degree matrix)"></a>度矩阵( Degree matrix)</h3><p>度矩阵(Degree matrix)是一个$D_{ii}$为节点$v_i$的度的对角矩阵，其定义如下所示：</p>
<script type="math/tex; mode=display">
D\in \mathbb{R}^{N \times N} ,D_{ii}=\Sigma_j A_{ij}</script><p><img src="https://res.cloudinary.com/leomars/image/upload/v1565750678/samples/mars/degree_matrix_iydlv3.jpg" alt></p>
<h3 id="邻域-Neighborhood"><a href="#邻域-Neighborhood" class="headerlink" title="邻域( Neighborhood)"></a>邻域( Neighborhood)</h3><p>邻域(Neighborhood)表示与某个节点有边连接的点集，其定义如下所示：$\mathcal{N}\left(v_{i}\right)=\left\{v_{j} | e_{i j} \in \mathcal{E}\right\}$。例如，节点1的领域为$\left\{2,5\right\}$。</p>
<h1 id="图上的学习任务"><a href="#图上的学习任务" class="headerlink" title="图上的学习任务"></a>图上的学习任务</h1><p>介绍完图的基本术语之后，我们来看看有了图结构数据，可以进行哪些机器学习的任务：</p>
<ol>
<li><p>图节点分类任务(Node Classification)：图中每个节点都有对应的特征，当我们已知一些节点的类别的时候，可以设计分类任务针对未知节点进行分类（半监督学习）。接下来要介绍的 GCN、GraphSAGE、GAT模型都是对图上的节点分类。</p>
</li>
<li><p>图边结构预测任务(Link Prediction)：图中的节点和节点之间的边关系可能在输入数据中能够采集到，而有些隐藏的边需要我们挖掘出来，这类任务就是对边的预测任务，也就是对节点和节点之间关系的预测。</p>
</li>
<li><p>图的分类(Clustering)：对于整个图来说，我们也可以对图分类，图分类又称为图的同构问题，基本思路是将图中节点的特征聚合起来作为图的特征，再进行分类。</p>
</li>
</ol>
<h1 id="图应用举例"><a href="#图应用举例" class="headerlink" title="图应用举例"></a>图应用举例</h1><p>下面是一个简单的电商的图，其包含卖家，商品和用户三个关键节点，其中：商品节点关联商品类别节点，用户节点关联注册 IP 节点和 注册地址节点。当用户在购买商品时，用户节点和商品节点就会关联交易节点，同时，交易节点也会关联用户下单时所对应的 IP 节点以及收获地址节点，对应的图结构如下图所示。</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565750678/samples/mars/example_flm8nd.jpg" alt></p>
<p>从图数据中节点间的关系以及特征，我们可以进行反欺诈以及商品推荐的操作。</p>
<ol>
<li><p>节点分类——反欺诈：因为图中每个节点都拥有自己的特征信息。通过该特征信息，我们可以构建一个风控系统，如果交易节点所关联的用户 IP 和收货地址与用户注册 IP 和注册地址不匹配，那么系统将有可能认为该用户存在欺诈风险。</p>
</li>
<li><p>边结构预测——商品推荐：图中每个节点都具有结构信息。如果用户频繁购买某种类别商品或对某种类别商品评分较高，那么系统就可以认定该用户对该类商品比较感兴趣，所以就可以向该用户推荐更多该类别的商品。</p>
</li>
</ol>
<p>总而言之，图数据的丰富应用价值促使更多的研究者加入图数据的研究当中，但是对图数据进行数据分析时，我们需要同时考虑到节点的特征信息以及结构信息。如果靠手工规则来提取，必将失去很多隐蔽和复杂的模式，那么有没有一种方法能自动化地同时学到图的特征信息与结构信息呢？这就是近年来兴起的机器学习的一个热点方向——图神经网络(Graph Neural Networks)。</p>
<h1 id="图神经网络-Graph-Neural-Networks"><a href="#图神经网络-Graph-Neural-Networks" class="headerlink" title="图神经网络(Graph Neural Networks)"></a>图神经网络(Graph Neural Networks)</h1><p>图神经网络(GNNs)是一种连接主义模型，它通过图节点之间的信息传递(message passing)来捕获图中的依赖关系。与标准神经网络不同的是，图神经网络可以收集一个节点周围任意深度邻节点的信息。近年来，图卷积网络(GCN)和门控图网络(GGNN)在众多领域取得了重大的成功。</p>
<h2 id="GNNs产生动机"><a href="#GNNs产生动机" class="headerlink" title="GNNs产生动机"></a>GNNs产生动机</h2><ol>
<li><p>卷积神经网络(CNNs)是GNN起源的首要动机，CNN只能应用于常规的欧几里得数据上（例如2-D的图片、1-D的文本），这些形式的数据可以被看成是图的特例化。随着对Graph和CNNs的深入分析，发现CNNs有三个关键点：局部连接、权值共享、多层网络。这对于GNN来说同样有重要的意义：1）图是最典型的局部连通结构；2）权值共享可以减少网络的计算量；3）多层结构是处理分层模式的关键，可以让网络捕获不同的特征。然而，从CNN到GNN的转变还面临着另一个问题，难以定义局部卷积核和池化操作。</p>
</li>
<li><p>图嵌入(Graph Embedding)，即如何将图中的节点、边和子图以低维向量的形式表现出来。DeepWalk基于表示学习，被认为是第一种图嵌入技术模型。还有基于SkipGram模型的Random Walk。以及node2vec，LINE和TADW等。然而以上的这些模型存在两个缺点：（1）图中节点之间不存在任何的参数共享，导致计算量与节点数量呈线性增长。（2）图嵌入技术缺乏泛化能力，导致不能处理动态图或推广至新的图。</p>
</li>
</ol>
<h2 id="原始GNN"><a href="#原始GNN" class="headerlink" title="原始GNN"></a>原始GNN</h2><p>在图中，每个节点的定义是由该节点的特征和相关节点来共同表示的。GNN的目标是训练出一个state embedding函数$h_v$，该函数包含了每个节点的邻域信息。</p>
<script type="math/tex; mode=display">
\mathbf{h}_{v}=f\left(\mathbf{x}_{v}, \mathbf{x}_{c o[v]}, \mathbf{h}_{n e[v]}, \mathbf{x}_{n e[v]}\right)\\
\mathbf{o}_{v}=g\left(\mathbf{h}_{v}, \mathbf{x}_{v}\right)</script><p>$h_v$是节点$v$的向量化表示，它可以被用来预测该节点的输出$\mathbf{o}_v$（例如节点的标签）。$f()$被称为local transition function，它被所有的节点共享，并根据输入的邻域信息来更新节点的状态。$x_v$是节点$v$的特征表示，$x_{co[v]}$是$v$节点上边的特征表示，$h_{ne[v]}$是该节点的状态，$x_{ne[v]}$是节点$v$周围节点的特征表示。$\mathbf{o}_{v}=g\left(\mathbf{h}_{v}, \mathbf{x}_{v}\right)$中$g(*)$被称为local output function，它是用来产生节点的输出的。</p>
<p>$\mathbf{H} =F(\mathbf{H}, \mathbf{X}) , \mathbf{O} =G\left(\mathbf{H}, \mathbf{X}_{N}\right)$，其中$H,O,X,X_N$为上述推广形式，代表图中的所有对象的堆叠形式。Banach的fixed point提出以后，GNN中state的迭代计算过程可以表示为：$\mathbf{H}^{t+1}=F\left(\mathbf{H}^{t}, \mathbf{X}\right)$，$\mathbf{H}^{t}$代表$\mathbf{H}$的第$t$次迭代的状态，$\mathbf{H}^{0}$代表其动态方程的初始状态。</p>
<p>对于一个GNN网络来说，其训练过程就是学习出函数$f(<em>)$和$g(</em>)$，$t_i$代表节点$i$的标签，GNN的优化过程为：</p>
<script type="math/tex; mode=display">
loss=\sum_{i=1}^{p}\left(\mathbf{t}_{i}-\mathbf{o}_{i}\right)</script><p>实验结果表明GNN对于结构化数据的建模十分有效，但仍然存在着诸多的不足：</p>
<ol>
<li>对于不动点隐藏状态的更新是十分低效的。如果放松对不动点的假设，多层GNN可以得到节点及其邻域的稳定表示；</li>
<li>GNN在迭代的过程中用相同的参数，然而大多标准网络在不同的网络层数使用不同的参数；</li>
<li>在原始的GNN中存在着一些无法有效建模的边信息特征。例如，在知识图谱中边代表关系类型，不同边的信息传递应该根据它们的类型有所不同。怎么样去学习边的隐藏状态也是一个重要的问题；</li>
<li>如果把重点放在节点的表示而不是图上，就不适合使用不动点，因为不动点上表示的分布会变得非常平滑，且每个节点的信息量也会减少。</li>
</ol>
<h2 id="GNNs变体"><a href="#GNNs变体" class="headerlink" title="GNNs变体"></a>GNNs变体</h2><p>在模型中，信息的传播步骤和输出步骤是获得节点或者边隐含状态的关键步骤。不同变体的GNN的聚合函数（用来聚合图中所有点的邻域信息，产生一个全局性的输出）和节点状态更新函数如下图所示：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565769030/samples/mars/different_variants_of_graph_neural_networks_fqrwma.jpg" alt></p>
<ul>
<li><p><strong>Convolution：GCN将卷积操作应用到图结构的数据上，主要分为Spectral method(<a href="https://arxiv.org/pdf/1609.02907" target="_blank" rel="noopener">GCN</a>)和Spatial Method(<a href="https://papers.nips.cc/paper/6703-inductive-representation-learning-on-large-graphs.pdf" target="_blank" rel="noopener">GraphSAGE</a>)两种方法，其目的都是对节点以及节点的邻近节点进行信息收集。</strong></p>
</li>
<li><p>Gate：使用GRU或者是LSTM这种带有门控机制的网络，来增强信息在图结构中的长期的传播。</p>
</li>
<li><p>Attention：GAT是一种图注意网络，它将注意力机制融入到了图传播的步骤中。GAT计算每个节点的隐藏状态，通过将Attention机制应用到邻近节点上。</p>
</li>
<li><p>Skip connection：研究发现更深的网络层数可以帮助网络在节点的邻域节点上获取到更多的信息。但通过实验也发现深层网络也会在网络传播中带来噪声信息，随着网络层数的加深，网络还会出现退化（残差连接）。基于图像领域的启发，residual network和highway network 这些Skip模型能够有效的处理这一问题。</p>
</li>
</ul>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565769529/samples/mars/propagation_steps_fmlvgw.jpg" alt></p>
<h2 id="GNNs的应用场景"><a href="#GNNs的应用场景" class="headerlink" title="GNNs的应用场景"></a>GNNs的应用场景</h2><p>GNNs被广泛应用于包括监督学习、半监督学习、无监督学习和强化学习等方向。论文中从三个不同的场景来分别阐述图网络的应用。（1）结构化场景：数据包含有很明确的关系结构，如物理系统、分子结构和知识图谱。（2）非结构化场景：数据不包含明确的关系结构，例如文本和图像等领域。（3）其他应用场景：例如生成式模型和组合优化模型。各个领域图网络的应用细节如下图所示：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565769528/samples/mars/applications_of_graph_neural_networks_zielmf.jpg" alt></p>
<h1 id="GNN必读论文"><a href="#GNN必读论文" class="headerlink" title="GNN必读论文"></a>GNN必读论文</h1><p><a href="https://github.com/thunlp/GNNPapers" target="_blank" rel="noopener">Must-read papers on GNN</a></p>
<h1 id="GNN系列规划"><a href="#GNN系列规划" class="headerlink" title="GNN系列规划"></a>GNN系列规划</h1><p>本文为GNN教程 [第一章 基础：三剑客] 的第一篇文章 [01 基础知识]，接下来将会介绍图神经网络的三个基本模型，使大家对它们有所了解。</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1565751960/samples/mars/gnn_fqjxaf.jpg" alt></p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/07/30/Introduction-to-PyTorch/" rel="next" title="Introduction to PyTorch">
                <i class="fa fa-chevron-left"></i> Introduction to PyTorch
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/09/01/GNN系列二：GCN/" rel="prev" title="GNN系列二：GCN">
                GNN系列二：GCN <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      
        <div id="gitment-container"></div>
      
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/messi.jpg" alt="MARS">
            
              <p class="site-author-name" itemprop="name">MARS</p>
              <p class="site-description motion-element" itemprop="description">自由是一种信仰</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">11</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">4</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/JyZhang10Mars" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="jyzhang.mars@gmail.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#欧几里得结构化数据"><span class="nav-number">1.</span> <span class="nav-text">欧几里得结构化数据</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#欧几里得空间"><span class="nav-number">1.1.</span> <span class="nav-text">欧几里得空间</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#常见的欧几里得结构化数据"><span class="nav-number">1.2.</span> <span class="nav-text">常见的欧几里得结构化数据</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#非欧几里得结构化数据"><span class="nav-number">2.</span> <span class="nav-text">非欧几里得结构化数据</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#非欧几里得空间"><span class="nav-number">2.1.</span> <span class="nav-text">非欧几里得空间</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#常见的非欧几里得结构化数据"><span class="nav-number">2.2.</span> <span class="nav-text">常见的非欧几里得结构化数据</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#图-Graph"><span class="nav-number">3.</span> <span class="nav-text">图(Graph)</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#图-Graph-的引入"><span class="nav-number">3.1.</span> <span class="nav-text">图(Graph)的引入</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#图-Graph-的定义"><span class="nav-number">3.2.</span> <span class="nav-text">图(Graph)的定义</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#图-Graph-的表示形式"><span class="nav-number">3.3.</span> <span class="nav-text">图(Graph)的表示形式</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#邻接矩阵-Adjacency-matrix"><span class="nav-number">3.3.1.</span> <span class="nav-text">邻接矩阵(Adjacency matrix)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#度矩阵-Degree-matrix"><span class="nav-number">3.3.2.</span> <span class="nav-text">度矩阵( Degree matrix)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#邻域-Neighborhood"><span class="nav-number">3.3.3.</span> <span class="nav-text">邻域( Neighborhood)</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#图上的学习任务"><span class="nav-number">4.</span> <span class="nav-text">图上的学习任务</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#图应用举例"><span class="nav-number">5.</span> <span class="nav-text">图应用举例</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#图神经网络-Graph-Neural-Networks"><span class="nav-number">6.</span> <span class="nav-text">图神经网络(Graph Neural Networks)</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#GNNs产生动机"><span class="nav-number">6.1.</span> <span class="nav-text">GNNs产生动机</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#原始GNN"><span class="nav-number">6.2.</span> <span class="nav-text">原始GNN</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#GNNs变体"><span class="nav-number">6.3.</span> <span class="nav-text">GNNs变体</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#GNNs的应用场景"><span class="nav-number">6.4.</span> <span class="nav-text">GNNs的应用场景</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#GNN必读论文"><span class="nav-number">7.</span> <span class="nav-text">GNN必读论文</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#GNN系列规划"><span class="nav-number">8.</span> <span class="nav-text">GNN系列规划</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">MARS</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Pisces</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
      <div id="needsharebutton-float">
        <span class="btn">
          <i class="fa fa-share-alt" aria-hidden="true"></i>
        </span>
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "box";
      
          pbOptions.boxForm = "horizontal";
      
          pbOptions.position = "bottomCenter";
      
          pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
      flOptions = {};
      
          flOptions.iconStyle = "box";
      
          flOptions.boxForm = "horizontal";
      
          flOptions.position = "middleRight";
      
          flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-float', flOptions);
    
  </script>

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
